package 剑指Offer.medium;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

public class 二叉树中和为某一值的路径 {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    class Solution {
        public List<List<Integer>> pathSum(TreeNode root, int target) {
            if (root == null) return null;
            List<List<Integer>> res = new LinkedList<>();
            LinkedList<Integer> path = new LinkedList<>();
            recur(root, res, path, target);
            return res;
        }

        public void recur(TreeNode root, List<List<Integer>> res, LinkedList<Integer> path, int target) {
            if (root == null) return;
            path.add(root.val);
            target -= root.val;
            if (target < 0) return;
            if (target == 0 && root.left == null && root.right == null){
                res.add(new LinkedList<>(path));
            }
            recur(root.left, res, path, target);
            recur(root.right, res, path, target);
            path.removeLast();
        }
    }
}
